Search for: All records

We give a randomized algorithm that approximates the number of independent sets in a dense, regular bipartite graph - in the language of approximate counting, we give an FPRAS for #BIS on the class of dense, regular bipartite graphs. Efficient counting algorithms typically apply to "high-temperature" problems on bounded-degree graphs, and our contribution is a notable exception as it applies to dense graphs in a low-temperature setting. Our methods give a counting-focused complement to the long line of work in combinatorial optimization showing that CSPs such as Max-Cut and Unique Games are easy on dense graphs via spectral arguments. Our contributions include a novel extension of the method of graph containers that differs considerably from other recent low-temperature algorithms. The additional key insights come from spectral graph theory and have previously been successful in approximation algorithms. As a result, we can overcome some limitations that seem inherent to the aforementioned class of algorithms. In particular, we exploit the fact that dense, regular graphs exhibit a kind of small-set expansion (i.e., bounded threshold rank), which, via subspace enumeration, lets us enumerate small cuts efficiently. 

In this work we consider the Steiner tree problem under Bilu-Linial stability. We give strong geometric struc- tural properties that need to be satisfied by stable in- stances. We then make use of, and strengthen, these geometric properties to show that 1.59-stable instances of Euclidean Steiner trees are polynomial-time solvable by showing it reduces to the minimum spanning tree problem. We also provide a connection between certain approximation algorithms and Bilu-Linial stability for Steiner trees. 

Abstract We determine the asymptotics of the number of independent sets of size $$\lfloor \beta 2^{d-1} \rfloor$$ in the discrete hypercube $$Q_d = \{0,1\}^d$$ for any fixed $$\beta \in (0,1)$$ as $$d \to \infty$$ , extending a result of Galvin for $$\beta \in (1-1/\sqrt{2},1)$$ . Moreover, we prove a multivariate local central limit theorem for structural features of independent sets in $$Q_d$$ drawn according to the hard-core model at any fixed fugacity $$\lambda>0$$ . In proving these results we develop several general tools for performing combinatorial enumeration using polymer models and the cluster expansion from statistical physics along with local central limit theorems.